/*  GStruct: data structure helpers for Java
 *  Copyright (C) 2011 Giulio Franco
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package gstruct.extensions;

import gstruct.sequential.DynamicallySizedIterable;
import gstruct.sequential.StaticallySizedIterable;
import gstruct.sequential.lazy.ConcatenateCollection;
import gstruct.sequential.lazy.LazyCollection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Utility functions for sequential data structures.
 * @author Giulio Franco <giulio_franco@msn.com>
 */
public final class Sequential {
	private static final int MAX_ARRAYLIST = 1000;
	
	private Sequential() { }
	
	/**
	 * Returns the minimum between the given parameters
	 * @param e1	First element
	 * @param args	Other elements
	 * @return		The element which is bigger, according to the comparison of the biggest element found so far.
	 * 							Ties are broken arbitrarily.
	 */
	public static <E extends Comparable<? super E>> E max(E e1, @SuppressWarnings("unchecked") E... args) {
		E tMax = e1;
		for (E e : args) {
			tMax = Single.max(tMax, e);
		}
		return tMax;
	}
	
	/**
	 * Returns the minimum between the given parameters
	 * @param e1	First element
	 * @param args	Other elements
	 * @return			The element which is bigger, according to the comparison of the last element checked so far.
	 * 							Ties are broken arbitrarily.
	 */
	public static <E extends Comparable<? super E>> E max2(E e1, @SuppressWarnings("unchecked") E... args) {
		E tMax = e1;
		for (E e : args) {
			tMax = Single.max(e, tMax);
		}
		return tMax;
	}
	
	
	/**
	 * Returns the minimum between the given parameters
	 * @param e1	First element
	 * @param args	Other elements
	 * @return			The element which is smaller, according to the comparison of the smallest element found so far.
	 * 							Ties are broken arbitrarily.
	 */
	public static <E extends Comparable<? super E>> E min(E e1, @SuppressWarnings("unchecked") E... args) {
		E tMin = e1;
		for (E e : args) {
			tMin = Single.min(tMin, e);
		}
		return tMin;
	}
	
	/**
	 * Returns the minimum between the given parameters
	 * @param e1	First element
	 * @param args	Other elements
	 * @return			The element which is smaller, according to the comparison of last element checked so far.
	 * 							Ties are broken arbitrarily.
	 */
	public static <E extends Comparable<? super E>> E min2(E e1, @SuppressWarnings("unchecked") E... args) {
		E tMin = e1;
		for (E e : args) {
			tMin = Single.min(e, tMin);
		}
		return tMin;
	}
	
	/**
	 * Returns the smallest element in an iterable collection
	 * @param collection	Iterable collection
	 * @return						Minimum element in the collection
	 */
	public static <E extends Comparable <? super E>> E min(Iterable<E> collection) {
		E min = null;
		for (E e : collection) {
			min = ((min == null) ? e : Single.min(min, e));
		}
		return min;
	}
	
	/**
	 * Returns the smallest element in an iterable collection, according to an external comparator
	 * @param collection	Iterable collection
	 * @param comparator	External comparator
	 * @return						Minimum element in the collection
	 */
	public static <E> E min(Iterable<? extends E> collection, Comparator<? super E> comparator) {
		E min = null;
		for (E e : collection) {
			min = ((min == null) ? e : Single.min(min, e, comparator));
		}
		return min;
	}
	
	/**
	 * Returns the biggest element in an iterable collection
	 * @param collection	Iterable collection
	 * @return						Minimum element in the collection
	 */
	public static <E extends Comparable <? super E>> E max(Iterable<E> collection) {
		E min = null;
		for (E e : collection) {
			min = ((min == null) ? e : Single.max(min, e));
		}
		return min;
	}
	
	/**
	 * Returns the biggest element in an iterable collection, according to an external comparator
	 * @param collection	Iterable collection
	 * @param comparator	External comparator
	 * @return						Minimum element in the collection
	 */
	public static <E> E max(Iterable<? extends E> collection, Comparator<? super E> comparator) {
		E min = null;
		for (E e : collection) {
			min = ((min == null) ? e : Single.max(min, e, comparator));
		}
		return min;
	}
	
	/**
	 * Creates an iterable collection, which only contains the element of the given one which satisfy predicate p.
	 * <p><b>Beware</b> that the returned collection is lazy, which means it occupies no memory,
	 * but it may yield unpredictable results if the collection is modified after the call to this method.
	 * For a non-lazy version, use {@link #filterNow}. 
	 * @param collection	Iterable collection
	 * @param p				Filter predicate
	 * @return				List of elements for which the predicate applies.
	 */
	public static <E> Iterable<E> filter(Iterable<E> collection, Predicate<? super E> p) {
		return new LazyCollection<>(collection, p);
	}
	
	/**
	 * Creates an iterable collection, which only contains the element of the given one which can be cast to class cls.
	 * <p><b>Beware</b> that the returned collection is lazy, which means it occupies no memory,
	 * but it may yield unpredictable results if the collection is modified after the call to this method.
	 * For a non-lazy version, use {@link #filterCastNow}. 
	 * @param collection	Iterable collection
	 * @param cls			Desired class
	 * @return				List of elements of type cls.
	 */
	@SuppressWarnings("unchecked")
	public static <E> Iterable<E> filterCast(Iterable<? super E> collection, Class<E> cls) {
		return (Iterable<E>) filter(collection, new CastPredicate<E>(cls));
	}
	
	/**
	 * Creates an iterable collection, which only contains the element of the given one which satisfy predicate p.
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param collection	Iterable collection
	 * @param p				Filter predicate
	 * @return				List of elements for which the predicate applies
	 */
	public static <E> List<E> filterNow(Iterable<E> collection, Predicate<? super E> p) {
		if (collection instanceof Collection) {
			return filterNow((Collection<E>)collection, p);
		}
		
		return filterInto(collection, p, new LinkedList<E>());
	}
	
	/**
	 * Creates an iterable collection, which only contains the element of the given one which satisfy predicate p.
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param collection	Iterable collection
	 * @param p				Filter predicate
	 * @return				List of elements for which the predicate applies
	 * 						The returned list is either an {@link ArrayList} or a {@link LinkedList}.
	 * 						The choice is based on the size of the original collection, and a fixed threshold.
	 * 						If you wish to have more control over the type of the generated list, consider using {@link #filterInto} 
	 */
	public static <E> List<E> filterNow(Collection<E> collection, Predicate<? super E> p) {
		List<E> res = ((collection.size() <= MAX_ARRAYLIST) ? new ArrayList<E>(collection.size()) : new LinkedList<E>());
		return filterInto(collection, p, res);	
	}
	
	/**
	 * Creates an iterable collection, which only contains the element of the given one which can be cast to class cls.
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param collection	Iterable collection
	 * @param cls			Desired class
	 * @return				List of elements of type cls.
	 */
	public static <E> List<E> filterCastNow(Iterable<? super E> collection, Class<E> cls) {
		if (collection instanceof Collection) {
			return filterCastNow((Collection<E>)collection, cls);
		}
		
		return filterCastInto(collection, cls, new LinkedList<E>());
	}
	
	/**
	 * Creates an iterable collection, which only contains the element of the given one which can be cast to class cls.
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param collection	Iterable collection
	 * @param cls			Desired class
	 * @return				List of elements of type cls.
	 * 						The returned list is either an {@link ArrayList} or a {@link LinkedList}.
	 * 						The choice is based on the size of the original collection, and a fixed threshold.
	 * 						If you wish to have more control over the type of the generated list, consider using {@link #filterInto} 
	 */
	public static <E> List<E> filterCastNow(Collection<? super E> collection, Class<E> cls) {
		List<E> res = ((collection.size() <= MAX_ARRAYLIST) ? new ArrayList<E>(collection.size()) : new LinkedList<E>());
		return filterCastInto(collection, cls, res);	
	}
	
	/**
	 * Adds the elements from a collection, that satisfied the given predicate, to a given collection
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param collection	Iterable collection
	 * @param p					Filter predicate
	 * @param dest				Destination collection
	 * 										It is responsibility of the caller to clean the collection before the call, if needed.
	 * @return						The collection dest
	 */
	public static <E, C extends Collection<? super E>> C filterInto(Iterable<E> collection, Predicate<? super E> p, C dest) {
		for (E e : collection) {
			if (p.appliesTo(e)) {
				dest.add(e);
			}
		}
		
		return dest;
	}
	
	/**
	 * Adds the elements from a collection, that satisfied the given predicate, to a given collection
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param collection	Iterable collection
	 * @param cls			Class that will be used to filter <code>collection</code>.
	 * 						Only elements that can be cast to <code>cls</code> will be added to <code>dest</code>
	 * @param dest			Destination collection
	 * 						It is responsibility of the caller to clean the collection before the call, if needed.
	 * @return				The collection dest
	 */
	public static <E, C extends Collection<? super E>> C filterCastInto(Iterable<? super E> collection, Class<E> cls, C dest) {
		for (Object e : collection) {
			if (cls.isInstance(e)) {
				dest.add(cls.cast(e));
			}
		}
		
		return dest;
	}
	
	/**
	 * Creates a collection which will return the concatenation of several collections
	 * <p><b>Beware</b> that the returned collection is lazy, which means it occupies no memory,
	 * but it may yield unpredictable results if the underlying collections are modified after the call to this method.
	 * For a non-lazy version, use {@link #concatenateNow}. 
	 * @param colls		Collections to concatenate
	 * @return			Concatenation of the given collections
	 */
	@SafeVarargs
	public static <E> Collection<E> concatenate(Collection<? extends E>... colls) {
		return new ConcatenateCollection<>(colls);
	}
	
	/**
	 * Creates a collection which will return the concatenation of several collections
	 * <p><b>Beware</b> that the returned collection is lazy, which means it occupies no memory,
	 * but it may yield unpredictable results if the underlying collections are modified after the call to this method.
	 * For a non-lazy version, use {@link #concatenateNow}. 
	 * @param colls		Collections to concatenate
	 * @return			Concatenation of the given collections
	 */
	@SuppressWarnings("unchecked")
	public static <E> Iterable<E> concatenate(Iterable<? extends E>... colls) {
		Collection<? extends E>[] mColls = new Collection[colls.length];
		for (int i = colls.length - 1; i >= 0; --i) {
			mColls[i] = sizedIterable(colls[i]);
		}
		return new ConcatenateCollection<>(mColls);
	}
	
	/**
	 * Creates a collection which will return the concatenation of two collections
	 * <p>For a less memory-expensive version, see {@link #concatenate}. 
	 * @param c1		First collection
	 * @param c2		Second collection
	 * @return				Concatenations of (in order) c1 and c2
	 */
	public static <E> Iterable<E> concatenateNow(Iterable<? extends E> c1, Iterable<? extends E> c2) {
		if (c1 instanceof Collection && c2 instanceof Collection) {
			return concatenateNow((Collection<? extends E>)c1, (Collection<? extends E>)c2);
		}
		
		return concatenateInto(c1, c2, new LinkedList<E>());
	}
	
	/**
	 * Creates a collection which will return the concatenation of two collections
	 * <p>For a less memory-expensive version, see {@link #concatenate}. 
	 * @param c1		First collection
	 * @param c2		Second collection
	 * @return				Concatenations of (in order) c1 and c2
	 */
	public static <E> List<E> concatenateNow(Collection<? extends E> c1, Collection<? extends E> c2) {
		List<E> res = new ArrayList<E>(c1.size() + c2.size());

		return concatenateInto(c1, c2, res);
	}
	
	/**
	 * Concatenates two collection into another
	 * <p>For a less memory-expensive version, see {@link #filter}. 
	 * @param c1		First collection
	 * @param c2		Second collection
	 * @param dest		Destination collection
	 * 								It is responsibility of the caller to clean the collection before the call, if needed.
	 * @return				The collection dest
	 */
	public static <E, C extends Collection<? super E>> C concatenateInto(Iterable<? extends E> c1, Iterable<? extends E> c2, C dest) {
		for (E e : c1) {
			dest.add(e);
		}
		for (E e : c2) {
			dest.add(e);
		}
		
		return dest;
	}
	
	/**
	 * Promotes an iterable to a collection, by calculating its size dynamically.
	 * <p><b>Beware</b> that the returned object is not thread safe.</p>
	 * If the size of the base iterable never changes, you can achieve better performance using {@link #sizedIterable(Iterable, boolean)}.
	 * @param base	Underlying iterable collection
	 * @return				Readonly collection backed by the base iterable.
	 */
	public static <E> Collection<E> sizedIterable(Iterable<E> base) {
		return new DynamicallySizedIterable<>(base);
	}
	
	/**
	 * Promotes an iterable to a collection, by calculating its size.
	 * @param base	Underlying iterable collection
	 * @param dynamic Set to true if you want the size to be recalculate each time {@link Collection#size() size()} is called.
	 * @return				Readonly collection backed by the base iterable.
	 */
	public static <E> Collection<E> sizedIterable(Iterable<E> base, boolean dynamic) {
		return (dynamic) ? new DynamicallySizedIterable<>(base) : new StaticallySizedIterable<>(base);
	}
	
	/**
	 * Returns the union of two collections
	 * @param c1	First collection
	 * @param c2	Second collection
	 * @return	Collection of elements <code>e</code> for which
	 * <pre>c1.contains(e) || c2.contains(e)</pre>
	 */
	public static <E> Collection<E> union(Iterable<? extends E> c1, Iterable<? extends E> c2) {
		int extSize = 0;
		if (c1 instanceof Collection) {
			extSize += ((Collection<? extends E>)c1).size();
		}
		if (c2 instanceof Collection) {
			extSize += ((Collection<? extends E>)c2).size();
		}
		
		Set<E> res = (extSize == 0) ? new HashSet<E>() : new HashSet<E>(extSize * 2);
		
		for (E e : c1) {
			res.add(e);
		}
		
		for (E e : c2) {
			res.add(e);
		}
		
		return res;
	}
	
	/**
	 * Returns the union of two collections
	 * @param c1	First collection
	 * @param c2	Second collection
	 * @return	Collection of elements <code>e</code> for which
	 * <pre>c1.contains(e) || c2.contains(e)</pre>
	 */
	public static <E> Collection<E> union(Collection<? extends E> c1, Collection<? extends E> c2) {
		Set<E> res = new HashSet<>((c1.size() + c2.size()) * 2);
		
		for (E e : c1) {
			res.add(e);
		}
		
		for (E e : c2) {
			res.add(e);
		}
		
		return res;
	}
	
	/**
	 * Returns the elements of minuend which are not in subtrahend
	 * @param minuend	First collection
	 * @param subtrahend	Second collection
	 * @return Collection of elements <code>e</code> for which
	 * <pre>minuend.contains(e) && !subtrahend.contains(e)</pre>
	 */
	public static <E> Collection<E> subtract(Iterable<? extends E> minuend, Iterable<? extends E> subtrahend) {
		int extSize = 0;
		if (minuend instanceof Collection) {
			extSize += ((Collection<? extends E>)minuend).size();
		}
		
		Set<E> res = (extSize == 0) ? new HashSet<E>() : new HashSet<E>(extSize * 2);
		
		for (E e : minuend) {
			res.add(e);
		}
		
		for (E e : subtrahend) {
			res.remove(e);
		}
		
		return res;
	}
	
	/**
	 * Returns the intersection of two collections
	 * @param c1	First collection
	 * @param c2	Second collection
	 * @return Collection of elements <code>e</code> for which
	 * <pre>c1.contains(e) && c2.contains(e)</pre>
	 */
	public static <E> Collection<E> intersection(Iterable<? extends E> c1, Iterable<? extends E> c2) {
		boolean c1IsSet = false;
		boolean c1IsColl = false;
		boolean c2IsColl = false;
		boolean c2IsSet = false;
		
		if (c1 instanceof Collection) {
			c1IsColl = true;
			c1IsSet = (c1 instanceof Set);
		}
		
		if (c2 instanceof Collection) {
			c2IsColl = true;
			c2IsSet = (c2 instanceof Set);
		}
		
		if (c1IsSet && c2IsColl) {
			return intersection((Collection<? extends E>)c2, (Collection<? extends E>) c1);
		} else if (c1IsColl && c2IsColl) {
			return intersection((Collection<? extends E>)c1, (Collection<? extends E>) c2);
		} else if (c1IsSet) {
			Collection<? extends E> cc2 = new StaticallySizedIterable<>(c2, Integer.MAX_VALUE);
			return intersection(cc2, (Collection<? extends E>)c1);
		} else if (c2IsSet) {
			Collection<? extends E> cc1 = new StaticallySizedIterable<>(c1, Integer.MAX_VALUE);
			return intersection(cc1, (Collection<? extends E>)c2);
		} else {
			return intersection(sizedIterable(c1), toSet(c2));
		}
	}
	
	/**
	 * Returns the intersection of two collections
	 * @param c1	First collection
	 * @param c2	Second collection
	 * @return Collection of elements <code>e</code> for which
	 * <pre>c1.contains(e) && c2.contains(e)</pre>
	 */
	public static <E> Collection<E> intersection(Collection<? extends E> c1, Collection<? extends E> c2) {
		if (!(c2 instanceof Set)) {
			if (c1 instanceof Set || c1.size() > c2.size()) {
				return intersection(c2, c1);
			} else {
				c2 = toSet(c2);
			}
		}
		
		
		Collection<E> res = new HashSet<E>(Math.min(c1.size(), c2.size()) * 2);
		
		for (E e : c1) {
			if (c2.contains(e)) {
				res.add(e);
			}
		}
		
		return res;
	}
	
	/**
	 * Returns the elements which are in exactly one of the two given collections
	 * @param c1	First collection
	 * @param c2	Second collection
	 * @return			Collection of the elements <code>e</code> for which
	 * <pre>c1.contains(e) ^ c2.contains(e)</pre>
	 */
	public static <E> Collection<E> delta(Iterable<? extends E> c1, Iterable<? extends E> c2) {
		return union(subtract(c1, c2), subtract(c2, c1));
	}
	
	/**
	 * Copies the content of an iterable collection to a set
	 * @param collection Iterable collection
	 * @return					  Set which contains all the elements of the given collection.
	 */
	public static <E> Set<E> toSet(Iterable<E> collection) {
		Set<E> res;
		
		if (collection instanceof Collection) {
			res = new HashSet<>(((Collection<E>)collection).size());
		} else {
			res = new HashSet<>();
		}
		
		for (E e : collection) {
			res.add(e);
		}
		
		return res;
	}
	
	/**
	 * Copies the content of an iterable collection to a List
	 * @param collection Iterable collection
	 * @return					  Set which contains all the elements of the given collection.
	 */
	public static <E> List<E> toList(Iterable<E> collection) {
		List<E> res;
		
		if (collection instanceof Collection) {
			res = new ArrayList<>(((Collection<E>)collection).size());
		} else {
			res = new ArrayList<>();
		}
		
		for (E e : collection) {
			res.add(e);
		}
		
		return res;
	}
	
	/**
	 * Applies a function to every element of the input collection
	 * @param it	Input collection
	 * @param m		Mapping function
	 * @return		List of results.
	 * 				The i-th element of the list is the result of m,
	 * 				applied to the i-th element returned by it.
	 */
	public static <E, D> List<D> map(
			Iterable<E> it, Mapper<? super E, ? extends D> m) {
		final List<D> res;
		if (it instanceof Collection) {
			res = new ArrayList<D>(((Collection<E>)it).size());
		} else {
			res = new ArrayList<D>();
		}
		
		for (E e : it) {
			res.add(m.map(e));
		}
		
		return res;
	}
}
